home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1987 / 11 / shammnov.lst < prev    next >
File List  |  1987-10-08  |  7KB  |  265 lines
  1.  
  2.  
  3.  
  4.  
  5. Listing 1.  Pascal function for the simple heuristic search in an unordered array. 
  6.  
  7.  
  8. FUNCTION Search1(VAR Data  : AnyArrayType; { input  }
  9.                  VAR Index : IntegerArray; { in/out } 
  10.                      NData : INTEGER;      { input  }
  11.                      Item  : ScalarType    { input  }) : INTEGER;
  12.  
  13. { function returns the index of the matching 
  14.   array, or zero if no match is found        }
  15.  
  16. VAR I, Tempo : INTEGER;
  17.  
  18. BEGIN
  19.     I := 1; 
  20.     { scan array }
  21.     WHILE (Item <> Data[ Index[I] ]) AND (I <= NData)  DO 
  22.             I := I + 1;
  23.  
  24.     IF I <= NData 
  25.     THEN BEGIN { match found }
  26.         Search1 := Index[I]; { returned result }
  27.         { Swap indices ? }
  28.         IF I > 1 THEN BEGIN
  29.             Tempo := Index[I];
  30.             Index[I] := Index[I-1];
  31.             Index[I-1] := Index[I];
  32.         END { IF }
  33.     END            
  34.     ELSE Search1 := 0; { not found }
  35.  
  36. END; { Search1 }
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46. Listing 2.  Pascal function for the heuristic search method for unordered arrays.
  47.  
  48.  
  49. FUNCTION Search2(VAR Data  : AnyArrayType; { input  }
  50.                  VAR Index : IntegerArray; { in/out } 
  51.                  VAR Loctn : SmallIntArray;{ in/out }
  52.                      NData : INTEGER;      { input  }
  53.                      Item  : ScalarType    { input  }) : INTEGER;
  54.  
  55. { function returns the index of the matching 
  56.   array, or zero if no match is found        }
  57.  
  58. CONST Factor = 0.7; { time-series factor }
  59.       { limits used to select search schemes }
  60.       UPPER_LIMIT = 0.65; { = 0.5 + 0.15 }
  61.       LOWER_LIMIT = 0.35; { = 0.5 - 0.15 }
  62.       { number of Loctn elements used in predicting the next 
  63.         matching location }
  64.       N = 4; 
  65.  
  66. VAR Continue : BOOLEAN;
  67.     I, J, Tempo, This_Location, Median, 
  68.     Skip, Result : INTEGER;
  69.     Next_Location, Power : REAL;
  70.  
  71.  
  72. PROCEDURE Swap_Indices(K : INTEGER);
  73. { Procedure used to swap indices }
  74. BEGIN
  75.     { Swap indices ? }
  76.     IF K > 1 THEN BEGIN
  77.         Tempo := Index[K];
  78.         Index[K] := Index[K-1];
  79.         Index[K-1] := Index[K];
  80.     END { IF }
  81. END;
  82.  
  83.  
  84. BEGIN
  85.     { Estimate the next location }
  86.     Next_Location := 0.0; { initialize next location }
  87.     Power := 1.0;
  88.     FOR I := N DOWNTO 1 DO BEGIN
  89.         Next_Location := Next_Location + Power * Loctn[I]; 
  90.         Power := Power * Factor;
  91.     END;
  92.     { calculate predicted next search location as a fraction }
  93.     Next_Location := (1.0 - Factor) * Next_Location  / NData; 
  94.  
  95.  
  96.     Result := 0; { default value for no match }
  97.  
  98.     IF Next_Location > UPPER_LIMIT THEN BEGIN
  99.         { Search last-to-first }
  100.         I := NData;
  101.         WHILE (Item <> Data[ Index[I] ]) AND (I > 0)  DO 
  102.             I := I - 1;
  103.  
  104.         IF I > 0 THEN BEGIN
  105.             Result := Index[I]; 
  106.             Swap_Indices(I); { swap indices }
  107.         END { IF }
  108.     END
  109.     ELSE IF Next_Location < LOWER_LIMIT THEN BEGIN
  110.         { Search first-to-last }
  111.         I := 1;
  112.         WHILE (Item <> Data[ Index[I] ]) AND (I <= NData)  DO 
  113.             I := I + 1;
  114.  
  115.         IF I <= NData THEN BEGIN
  116.             Result := Index[I]; 
  117.             Swap_Indices(I); { swap indices }
  118.         END { IF }
  119.     END
  120.     ELSE 
  121.         { Perform bidirectional search starting at the middle }
  122.         Median := NData div 2;
  123.         IF Item <> Data[ Index[Median] ] THEN BEGIN
  124.             Skip := 1;
  125.             Continue := TRUE;
  126.             REPEAT
  127.                 I := Median + Skip;
  128.                 IF I <= NData THEN 
  129.                     IF Item = Data[ Index[I] ] THEN BEGIN
  130.                         Result := Index[I];
  131.                         Continue := FALSE;
  132.                         Swap_Indices(I); { swap indices }
  133.                     END; { IF }
  134.  
  135.                 J := Median - Skip;
  136.                 IF J > 0 THEN 
  137.                     IF Item = Data[ Index[J] ] THEN BEGIN
  138.                         Result := Index[J];
  139.                         Continue := FALSE;
  140.                         Swap_Indices(J); { swap indices }
  141.                     END; { IF }
  142.  
  143.                 IF (I > NData) AND (J < 1) THEN { out of bounds }
  144.                     Continue := FALSE;
  145.  
  146.                 Skip := Skip + 1;
  147.  
  148.             UNTIL (NOT Continue);
  149.             
  150.         END
  151.         ELSE BEGIN
  152.             Result := Index[Median];
  153.             Swap_Indices(Media)
  154.         END; { IF }
  155.     END; { IF }
  156.  
  157.     IF Result > 0 THEN BEGIN
  158.         { Update location array }
  159.         FOR I := 1 TO N-1 DO 
  160.             Loctn[I] := Loctn[I+1];
  161.         Loctn[N] := Result
  162.     END; { IF }
  163.  
  164.     Search2 := Result; { return result }        
  165.  
  166.  
  167. END; { Search 2 }
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176. Listing 3.  Pascal code for function implementing the first heuristic search method for fixed ordered arrays.
  177.  
  178.  
  179. PROCEDURE Initialize(VAR Data  : AnyArrayType; { input  }
  180.                      VAR Table : RecordArray;  { in/out }
  181.                      TableSize : INTEGER;      { input  } 
  182.                          NData : INTEGER       { input  });
  183.  
  184. { initialize index table by inserting data at equal intervals }
  185. { 
  186.  
  187.     TYPE TableRecord = RECORD 
  188.             Key : ScalarType;
  189.             Index : INTEGER;
  190.          END;
  191.  
  192.          RecordArray = ARRAY[1..MAX_TABLE_SIZE] OF TableRecord;       
  193. }
  194.  
  195. VAR I, J, Delta : INTEGER;
  196.  
  197. BEGIN
  198.     Delta := NData div TableSize;
  199.     J := 1;
  200.     FOR I := 1 TO TableSize DO BEGIN
  201.         Table[I].Key := Data[J];
  202.         Table[I].Index := J;
  203.         J := J + Delta;
  204.     END;
  205.  
  206. END; { initialize }
  207.  
  208.  
  209.  
  210. FUNCTION Search3(VAR Data  : AnyArrayType; { input  }
  211.                  VAR Table : RecordArray;  { in/out }
  212.                  TableSize,                { input  } 
  213.                      NData : INTEGER;      { input  }
  214.                      Item  : ScalarType    { input  }) : INTEGER;
  215.  
  216. VAR Found, NoMatch : BOOLEAN;
  217.     First, Last, I, K, Result : INTEGER;
  218.     
  219.  
  220. BEGIN
  221.     Result := 0; { initialize result with default value }
  222.  
  223.     { Search for Item in index table }
  224.     I := 1;
  225.     WHILE (Item > Table[I].Key) AND (I <= TableSize) DO 
  226.         I := I + 1;
  227.  
  228.     Found := FALSE;
  229.  
  230.     IF I <= TableSize 
  231.         THEN Found := (Item = Table[I].Key)
  232.         ELSE I := I - 1;
  233.  
  234.     IF Found 
  235.     THEN 
  236.         Result := Table[I].Index
  237.     ELSE
  238.         { Get range for search limits }
  239.         First := Table[I-1].Index;
  240.         Last := Table[I].Index;
  241.         K := I-1;
  242.         NoMatch := TRUE;
  243.         I := First;
  244.         WHILE (I <= Last) AND NoMatch DO 
  245.             IF Item <> Data[I].Key THEN I := I + 1
  246.                                    ELSE NoMatch := FALSE;
  247.     
  248.  
  249.         IF NOT NoMatch THEN BEGIN
  250.             Result := Table[I].Index; { store result }
  251.             
  252.             IF K > 1 THEN BEGIN { update table entry }
  253.                 Table[K].Key := Item;
  254.                 Table[K].Index := Result
  255.             END; { IF }
  256.  
  257.         END; { IF }
  258.  
  259.     END; { IF }
  260.  
  261.     Search3 := Result { return result }
  262.  
  263. END; { Search3 }
  264.  
  265.